# 作者: 赵若云
# 2025年02月25日15时12分14秒
# 3478783573@qq.com


class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    def __init__(self):
        self.root = None
        self.queue = []

    def add_node(self, elem):
        new_node = Node(elem)
        self.queue.append(new_node)
        if self.root is None:
            self.root = new_node
        else:
            if self.queue[0].lchild is None:
                self.queue[0].lchild = new_node
            else:
                self.queue[0].rchild = new_node
                self.queue.pop(0)

    def pre_order(self, current_node):
        if current_node:  # 这个判断条件不能少
            print(current_node.elem, end=' ')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def level_order(self):
        queue = []
        queue.append(self.root)
        while queue:
            current_node = queue.pop(0)
            print(current_node.elem, end=" ")
            if current_node.lchild:
                queue.append(current_node.lchild)
            if current_node.rchild:
                queue.append(current_node.rchild)



if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 11):
        tree.add_node(i)

    tree.pre_order(tree.root)
    print()
    tree.level_order()
